package 每日一题;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/the-number-of-weak-characters-in-the-game/
 */
public class _1996_游戏中弱角色的数量 {
    /**
     * 排序
     * @param properties 目标二维数组
     * @return int
     */
    public int numberOfWeakCharacters(int[][] properties) {
        // 先将参数从 0 开始依次向上排,如果相等，则比较第二个值进行排序
        Arrays.sort(properties, (o1, o2) -> {
            return o1[0] == o2[0] ? (o1[1] - o2[1]) : (o2[0] - o1[0]);
        });
        int maxDef = 0;
        int ans = 0;
        // 遍历比较properties的第二个数，因为第一个数已经排序完成，因此如果第二个数还小于最大的数，则ans++
        for (int[] p : properties) {
            if (p[1] < maxDef) {
                ans++;
            } else {
                maxDef = p[1];
            }
        }
        return ans;
    }

    /**
     * 单调栈
     * @param properties 目标二维数组
     * @return int
     */
    public int numberOfWeakCharacters2(int[][] properties) {
        Arrays.sort(properties, (o1, o2) -> {
            return o1[0] == o2[0] ? (o2[1] - o1[1]) : (o1[0] - o2[0]);
        });
        int ans = 0;
        Deque<Integer> st = new ArrayDeque<Integer>();
        for (int[] p : properties) {
            while (!st.isEmpty() && st.peek() < p[1]) {
                st.pop();
                ans++;
            }
            st.push(p[1]);
        }
        return ans;
    }
}
